Microprocessor designers employ many techniques to increase microprocessor performance. Most microprocessors operate using a clock signal running at a fixed frequency. Each clock cycle the circuits of the microprocessor perform their respective functions. According to Hennessy and Patterson (see Computer Architecture: A Quantitative Approach, 3rd Edition), the true measure of a microprocessor's performance is the time required to execute a program or collection of programs. From this perspective, the performance of a microprocessor is a function of its clock frequency, the average number of clock cycles required to execute an instruction (or alternately stated, the average number of instructions executed per clock cycle), and the number of instructions executed in the program or collection of programs. Semiconductor scientists and engineers are continually making it possible for microprocessors to run at faster clock frequencies, chiefly by reducing transistor size, resulting in faster switching times. The number of instructions executed is largely fixed by the task to be performed by the program, although it is also affected by the instruction set architecture of the microprocessor. Large performance increases have been realized by architectural and organizational notions that improve the instructions per clock cycle, in particular by notions of parallelism.
One notion of parallelism that has improved the instructions per clock cycle, as well as the clock frequency, of microprocessors is pipelining, which overlaps execution of multiple instructions within pipeline stages of the microprocessor. In an ideal situation, each clock cycle one instruction moves down the pipeline to a new stage, which performs a different function on the instructions. Thus, although each individual instruction takes multiple clock cycles to complete, because the multiple cycles of the individual instructions overlap, the average clocks per instruction is reduced. The performance improvements of pipelining may be realized to the extent that the instructions in the program permit it, namely to the extent that an instruction does not depend upon its predecessors in order to execute and can therefore execute in parallel with its predecessors, which is commonly referred to as instruction-level parallelism. Another way in which instruction-level parallelism is exploited by contemporary microprocessors is the issuing of multiple instructions for execution per clock cycle. These microprocessors are commonly referred to as superscalar microprocessors.
What has been discussed above pertains to parallelism at the individual instruction-level. However, the performance improvement that may be achieved through exploitation of instruction-level parallelism is limited. Various constraints imposed by limited instruction-level parallelism and other performance-constraining issues have recently renewed an interest in exploiting parallelism at the level of blocks, or sequences, or streams of instructions, commonly referred to as thread-level parallelism. A thread is simply a sequence, or stream, of program instructions. A multithreaded microprocessor concurrently executes multiple threads according to some scheduling policy that dictates the fetching and issuing of instructions of the various threads, such as interleaved, blocked, or simultaneous multithreading. A multithreaded microprocessor typically allows the multiple threads to share the functional units of the microprocessor (e.g., instruction fetch and decode units, caches, branch prediction units, and load/store, integer, floating-point, SIMD, etc. execution units) in a concurrent fashion. However, multithreaded microprocessors include multiple sets of resources, or contexts, for storing the unique state of each thread, such as multiple program counters and general purpose register sets, to facilitate the ability to quickly switch between threads to fetch and issue instructions.
One example of a performance-constraining issue addressed by multithreading microprocessors is the fact that accesses to memory outside the microprocessor that must be performed due to a cache miss typically have a relatively long latency. It is common for the memory access time of a contemporary microprocessor-based computer system to be between one and two orders of magnitude greater than the cache hit access time. Instructions dependent upon the data missing in the cache are stalled in the pipeline waiting for the data to come from memory. Consequently, some or all of the pipeline stages of a single-threaded microprocessor may be idle performing no useful work for many clock cycles. Multithreaded microprocessors may solve this problem by issuing instructions from other threads during the memory fetch latency, thereby enabling the pipeline stages to make forward progress performing useful work, somewhat analogously to, but at a finer level of granularity than, an operating system performing a task switch on a page fault. Other examples of performance-constraining issues addressed by multithreading microprocessors are pipeline stalls and their accompanying idle cycles due to a branch misprediction and concomitant pipeline flush, or due to a data dependence, or due to a long latency instruction such as a divide instruction, floating-point instruction, or the like. Again, the ability of a multithreaded microprocessor to issue instructions from other threads to pipeline stages that would otherwise be idle may significantly reduce the time required to execute the program or collection of programs comprising the threads.
As may be observed from the foregoing, a processor concurrently executing multiple threads may reduce the time required to execute a program or collection of programs comprising the multiple threads. In particular, when one thread is stalled, the multithreading processor may issue instructions from other threads to utilize available instruction execution bandwidth. However, in a scalar microprocessor with a single execution pipeline, if the pipeline is stalled for one thread it is stalled for all threads. Even though other threads may have instructions that are not dependent upon the stalled thread, the instruction execution bandwidth of the processor is wasted because the instructions of other threads cannot be executed since the scalar pipeline is stalled. Furthermore, even in a superscalar processor with multiple execution pipelines, the instruction execution bandwidth of the stalled pipeline is wasted because the instructions of other threads cannot be executed by the stalled execution pipeline.
One solution to this problem has been described in U.S. application Ser. No. 11/051,979, which is to flush the execution pipeline that is stalled (and particularly, to flush on the stalled thread) and retry the flushed instructions after the stalling condition is no longer present, e.g., when a missing load data is returned, or a long-executing instruction result is available. However, there is a cost of retrying instructions. Part of the cost is re-fetching the instructions. If the instructions are still present in the instruction cache, then many times the additional clock cycles required to re-fetch the instructions may be hidden by the time taken for the stall condition to subside. However, a possibility exists that the data will no longer be in the instruction cache, thereby introducing another large system memory latency, which may have the secondary effect of causing the execution pipelines to be starved for executable instructions. Even if the instructions are still present in the instruction cache, the re-fetches may consume precious instruction fetch bandwidth. Furthermore, if the condition originally causing the stall subsides shortly after the flush (e.g., missing load data is returned, or a long instruction completes), which may be a non-negligible percentage of the time, then the flushed instructions may not have been re-fetched and ready for re-issuance, thereby potentially causing the execution pipelines to be starved for executable instructions. Therefore, what is needed is an apparatus and method for reducing the need to re-fetch instructions flushed in response to a pipeline stall.